Conditioning of Random Block Subdictionaries with Applications to Block-Sparse Recovery and Regression

摘要

The linear model, in which a set of observations is assumed to be given by alinear combination of columns of a matrix, has long been the mainstay of thestatistics and signal processing literature. One particular challenge forinference under linear models is understanding the conditions on the dictionaryunder which reliable inference is possible. This challenge has attractedrenewed attention in recent years since many modern inference problems dealwith the "underdetermined" setting, in which the number of observations is muchsmaller than the number of columns in the dictionary. This paper makes severalcontributions for this setting when the set of observations is given by alinear combination of a small number of groups of columns of the dictionary,termed the "block-sparse" case. First, it specifies conditions on thedictionary under which most block subdictionaries are well conditioned. Thisresult is fundamentally different from prior work on block-sparse inferencebecause (i) it provides conditions that can be explicitly computed inpolynomial time, (ii) the given conditions translate into near-optimal scalingof the number of columns of the block subdictionaries as a function of thenumber of observations for a large class of dictionaries, and (iii) it suggeststhat the spectral norm and the quadratic-mean block coherence of the dictionary(rather than the worst-case coherences) fundamentally limit the scaling ofdimensions of the well-conditioned block subdictionaries. Second, this paperinvestigates the problems of block-sparse recovery and block-sparse regressionin underdetermined settings. Near-optimal block-sparse recovery and regressionare possible for certain dictionaries as long as the dictionary satisfieseasily computable conditions and the coefficients describing the linearcombination of groups of columns can be modeled through a mild statisticalprior.